热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

总数|小规模算法动态规划第3讲:LeetCode62不同路径详解|从自顶向下到自底向上的动态规划方法分析

篇首语:本文由编程笔记#小编为大家整理,主要介绍了算法动态规划 ③ ( LeetCode 62.不同路径 | 问题分析 | 自顶向下的动态规划 | 自底向上的动态规划 )相关的知识,希望对你有一定的参

篇首语:本文由编程笔记#小编为大家整理,主要介绍了算法动态规划 ③ ( LeetCode 62.不同路径 | 问题分析 | 自顶向下的动态规划 | 自底向上的动态规划 )相关的知识,希望对你有一定的参考价值。



文章目录


  • 一、问题分析
  • 二、自顶向下的动态规划
    • 1、动态规划状态 State
    • 2、动态规划初始化 Initialize
    • 3、动态规划方程 Function
    • 4、动态规划答案 Answer
    • 5、代码示例

  • 三、自底向上的动态规划
    • 1、动态规划状态 State
    • 2、动态规划初始化 Initialize
    • 3、动态规划方程 Function
    • 4、动态规划答案 Answer
    • 5、代码示例


LeetCode 62.不同路径 : https://leetcode.cn/problems/unique-paths

一个机器人位于一个 m x n 网格 左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能 向下或者向右 移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?










一、问题分析



动态规划 可以解决 三类问题 :


  • 求最值 : 最大值 , 最小值 等 ;
    • 大规模问题的结果 由 小规模问题 的计算结果 相加
    • 大规模问题的结果 由 小规模问题 的计算结果 取最大值
    • 大规模问题的结果 由 小规模问题 的计算结果 取最小值
  • 可行性 : 是否可行 ;
    • 大规模问题的结果 由 小规模问题 的计算结果 必须全部可行
    • 大规模问题的结果 由 小规模问题 的计算结果 只要有一个可行即可
    • 大规模问题的结果 由 小规模问题 的计算结果 没有可行结果
  • 方案数 :
    • 大规模问题的结果 由 小规模问题 的计算结果 可行方案总数


在本示例中 , 使用动态规划 求的是 可行方案总数 ;



在 m x n 网格中 , 只能向右走 或 向下走 ;

将 大规模问题 拆解成 小规模问题 时 , 其依赖关系 是有 方向性的 ;










二、自顶向下的动态规划




1、动态规划状态 State



使用 二维数组 dp 保存 动态规划的 状态 State ,

dp[i][j] 表示 从 (0, 0) 位置出发 , 到 (i, j) 位置的方案总数 ;




2、动态规划初始化 Initialize



初始位置 (0 , 0) 位置 的方案数 , 肯定为 1 , 因此有 dp[0][0] = 1 ;

最左侧的一列 , 只能向下走 , 其方案数也为 1 , 因此有 dp[i][0] = 1 ;

最上方的一排 , 只能向右走 , 其方案数也为 1 , 因此有 dp[0][j] = 1 ;




3、动态规划方程 Function



由于 运动时 , 只能 向右 或 向下 走 , 走到 (i , j) 只能是从 左边 (i - 1, j) 上边 (i , j-1) 位置走过来 ,

这里可以得到依赖关系 : dp[i][j] = dp[i-1][j] + dp[i][j-1]




4、动态规划答案 Answer



最终的 从 左上角 (0 , 0) 位置 走到 右下角 (m , n) 位置 的方案总数就是 状态 State 中的 dp[m - 1][n - 1] 数值 ;




5、代码示例



代码示例 :

public class Solution
/**
* 不同路径
* @param m 网格行数
* @param n 网格列数
* @return
*/

public int uniquePaths(int m, int n)
// 1. 动态规划状态 State
// dp[i][j] 表示 从 (0, 0) 位置出发 , 到 (i, j) 位置的方案总数 ;
int[][] dp = new int[m][n];
// 2. 动态规划初始化 Initialize
// 最左侧的一列 , 只能向下走 , 其方案数也为 1 , 因此有 dp[i][0] = 1 ;
for (int i &#61; 0; i < m; &#43;&#43;i)
dp[i][0] &#61; 1;

// 最上方的一排 , 只能向右走 , 其方案数也为 1 , 因此有 dp[0][j] &#61; 1 ;
for (int j &#61; 0; j < n; &#43;&#43;j)
dp[0][j] &#61; 1;

// 3. 动态规划方程 Function
// 运动时 , 只能 向右 或 向下 走 ,
// 走到 (i , j) 只能是从 左边 (i - 1, j) 或 上边 (i , j-1) 位置走过来 ,
// 这里可以得到依赖关系 : dp[i][j] &#61; dp[i-1][j] &#43; dp[i][j-1]
for (int i &#61; 1; i < m; &#43;&#43;i)
for (int j &#61; 1; j < n; &#43;&#43;j)
dp[i][j] &#61; dp[i - 1][j] &#43; dp[i][j - 1];


// 4. 动态规划答案 Answer
// 最终的 从 左上角 (0 , 0) 位置 走到 右下角 (m , n) 位置
// 的方案总数就是 状态 State 中的 dp[m - 1][n - 1] 数值 ;
return dp[m - 1][n - 1];

public static void main(String[] args)
int minTotal &#61; new Solution().uniquePaths(3, 7);
System.out.println("3 x 7 网格方案数为 : " &#43; minTotal);


执行结果 :

3 x 7 网格方案数为 : 28










三、自底向上的动态规划




1、动态规划状态 State



使用 二维数组 dp 保存 动态规划的 状态 State ,

dp[i][j] 表示 从 (i , j) 位置出发 , 到 (m - 1, n - 1) 位置的方案总数 ;




2、动态规划初始化 Initialize



终点位置 (m - 1, n - 1) 位置 到 (m - 1, n - 1) 位置的方案总数 , 肯定为 1 , 因此有 dp[m - 1][n - 1] &#61; 1 ;

最右侧的一列 , 只能向下走 , 到 (m - 1, n - 1) 位置的方案总数 也为 1 , 因此有 dp[i][n - 1] &#61; 1 ;

最下方的一排 , 只能向右走 , 其 到 (m - 1, n - 1) 位置的方案总数 方案数也为 1 , 因此有 dp[m - 1][j] &#61; 1 ;




3、动态规划方程 Function



由于 运动时 , 只能 向右 或 向下 走 , 从 (i , j) 走到 ( m - 1 , n - 1 ) 只能是走 右边 (i &#43; 1, j) 下边 (i , j &#43; 1) 位置 ,

即 从 (i , j) 走到 ( m - 1 , n - 1 ) 位置的方案数 , 依赖于


  • 从 (i &#43; 1, j) 走到 ( m - 1 , n - 1 ) 位置的方案数
  • 从 (i , j &#43; 1) 走到 ( m - 1 , n - 1 ) 位置的方案数

之和 ;

这里可以得到依赖关系 : dp[i][j] &#61; dp[i&#43;1][j] &#43; dp[i][j&#43;1]




4、动态规划答案 Answer



最终的 从 左上角 (0 , 0) 位置 走到 右下角 (m , n) 位置 的方案总数就是 状态 State 中的 dp[0][0] 数值 ;




5、代码示例



代码示例 :

public class Solution
/**
* 不同路径
* &#64;param m 网格行数
* &#64;param n 网格列数
* &#64;return
*/

public int uniquePaths(int m, int n)
// 1. 动态规划状态 State
// dp[i][j] 表示 从 (i , j) 位置出发 , 到 (m - 1, n - 1) 位置的方案总数 ;
int[][] dp &#61; new int[m][n];
// 2. 动态规划初始化 Initialize
// 最右侧的一列 , 只能向下走 , 到 (m - 1, n - 1) 位置的方案总数 也为 1 ,
// 因此有 dp[i][n - 1] &#61; 1 ;
for (int i &#61; 0; i < m; &#43;&#43;i)
dp[i][n - 1] &#61; 1;

// 最下方的一排 , 只能向右走 , 其 到 (m - 1, n - 1) 位置的方案总数 方案数也为 1 ,
// 因此有 dp[m - 1][j] &#61; 1 ;
for (int j &#61; 0; j < n; &#43;&#43;j)
dp[m - 1][j] &#61; 1;

// 3. 动态规划方程 Function
// 由于 运动时 , 只能 向右 或 向下 走 ,
// 从 (i , j) 走到 ( m - 1 , n - 1 ) 只能是走 右边 (i &#43; 1, j) 或 下边 (i , j &#43; 1) 位置 ,
// 即 从 (i , j) 走到 ( m - 1 , n - 1 ) 位置的方案数 , 依赖于
// 从 (i &#43; 1, j) 走到 ( m - 1 , n - 1 ) 位置的方案数
// 从 (i , j &#43; 1) 走到 ( m - 1 , n - 1 ) 位置的方案数
// 之和
for (int i &#61; m - 2; i >&#61; 0; i--)
for (int j &#61; n - 2; j >&#61; 0; j--)
dp[i][j] &#61; dp[i &#43; 1][j] &#43; dp[i][j &#43; 1];


// 4. 动态规划答案 Answer
// 最终的 从 左上角 (0 , 0) 位置 走到 右下角 (m , n) 位置
// 的方案总数就是 状态 State 中的 dp[0][0] 数值 ;
return dp[0][0];

public static void main(String[] args)
int minTotal &#61; new Solution().uniquePaths(3, 7);
System.out.println("3 x 7 网格方案数为 : " &#43; minTotal);


执行结果 :

3 x 7 网格方案数为 : 28


推荐阅读
  • 探索偶数次幂二项式系数的求和方法及其数学意义 ... [详细]
  • 本文介绍了UUID(通用唯一标识符)的概念及其在JavaScript中生成Java兼容UUID的代码实现与优化技巧。UUID是一个128位的唯一标识符,广泛应用于分布式系统中以确保唯一性。文章详细探讨了如何利用JavaScript生成符合Java标准的UUID,并提供了多种优化方法,以提高生成效率和兼容性。 ... [详细]
  • PHP中函数名、常量名和变量名大小写转换及规范详解
    在PHP编程中,初学者常常会遇到关于函数名、常量名和变量名大小写的问题。本文详细解析了PHP中这些名称的大小写敏感性及其命名规范,帮助开发者更好地理解和使用PHP。具体而言,文章探讨了PHP中的常量名是否区分大小写,自定义函数名的大小写敏感性,以及类名的大小写规则。此外,还提供了实用的代码示例和最佳实践,以确保代码的可读性和一致性。 ... [详细]
  • 本文详细解析了九度编程平台上的斐波那契数列高效算法挑战(题目编号:1387)。该挑战要求在1秒的时间限制和32兆的内存限制下,设计出高效的斐波那契数列计算方法。通过多种算法的对比和性能分析,本文提供了优化方案,帮助参赛者在限定资源条件下实现高效计算。 ... [详细]
  • HBase Java API 进阶:过滤器详解与应用实例
    本文详细探讨了HBase 1.2.6版本中Java API的高级应用,重点介绍了过滤器的使用方法和实际案例。首先,文章对几种常见的HBase过滤器进行了概述,包括列前缀过滤器(ColumnPrefixFilter)和时间戳过滤器(TimestampsFilter)。此外,还详细讲解了分页过滤器(PageFilter)的实现原理及其在大数据查询中的应用场景。通过具体的代码示例,读者可以更好地理解和掌握这些过滤器的使用技巧,从而提高数据处理的效率和灵活性。 ... [详细]
  • 捕获并处理用户输入数字时的异常,提供详细的错误提示与指导
    在用户输入数字时,程序能够有效捕获并处理各种异常情况,如非法字符或格式错误,并提供详尽的错误提示和操作指导,确保用户能够准确输入有效的数字数据。通过这种方式,不仅提高了程序的健壮性和用户体验,还减少了因输入错误导致的系统故障。具体实现中,使用了Java的异常处理机制,结合Scanner类进行输入读取和验证,确保了输入的合法性和准确性。 ... [详细]
  • C++入门必备:首个博客知识点汇总
    本文总结了C++初学者需要掌握的关键知识点,特别强调了成员类型的区分。其中,protected成员与private成员在本类中的作用相同,但protected成员允许派生类的成员函数访问,而private成员则不允许。此外,文章还介绍了其他重要的C++基础概念,如类的构造函数、析构函数以及继承机制,为初学者提供了一个全面的学习指南。 ... [详细]
  • PHP 数组逆序排列方法及常用排序函数详解 ... [详细]
  • 本文深入探讨了二叉树路径和问题的算法优化方法。具体而言,给定一棵二叉树,需要找出所有从根节点到叶节点的路径,其中各节点值的总和等于指定的目标值。通过详细分析和优化,提出了一种高效的解决方案,并通过多个样例验证了其有效性和性能。 ... [详细]
  • 二叉树的直径是指树中任意两个叶节点之间最长路径上的节点数量。本文深入解析了计算二叉树直径的算法,并提出了一种优化方法,以提高计算效率和准确性。通过详细的案例分析和性能对比,展示了该优化算法在实际应用中的优势。 ... [详细]
  • 本文全面解析了 gRPC 的基础知识与高级应用,从 helloworld.proto 文件入手,详细阐述了如何定义服务接口。例如,`Greeter` 服务中的 `SayHello` 方法,该方法在客户端和服务器端的消息交互中起到了关键作用。通过实例代码,读者可以深入了解 gRPC 的工作原理及其在实际项目中的应用。 ... [详细]
  • 本文提出了一种高效的数据结构与算法,旨在解决超大整数(超出常规 `long` 类型范围)的加法运算问题。通过引入自定义的数据结构,该方法能够有效地存储和处理任意大小的整数,并在保证计算精度的同时,显著提升运算效率。实验结果表明,该方法在处理大规模数据时表现出色,具有较高的实用价值。 ... [详细]
  • 字节码开发笔记:深入解析与应用技巧 ... [详细]
  • 在处理大图片时,PHP 常常会遇到内存溢出的问题。为了避免这种情况,建议避免使用 `setImageBitmap`、`setImageResource` 或 `BitmapFactory.decodeResource` 等方法直接加载大图。这些函数在处理大图片时会消耗大量内存,导致应用崩溃。推荐采用分块处理、图像压缩和缓存机制等策略,以优化内存使用并提高处理效率。此外,可以考虑使用第三方库如 ImageMagick 或 GD 库来处理大图片,这些库提供了更高效的内存管理和图像处理功能。 ... [详细]
  • 开发笔记:深入解析Android自定义控件——Button的72种变形技巧
    开发笔记:深入解析Android自定义控件——Button的72种变形技巧 ... [详细]
author-avatar
mobiledu2502856411
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有